package leetcode_2301_2400;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeeCode_2370_slow {
    public static void main(String[] args) {
//        System.out.println(longestIdealString("acfgbd", 2));
//        System.out.println(longestIdealString("abcd", 3));
        System.out.println(longestIdealString("pvjcci", 4));
    }
    private static int longestIdealString(String s, int k) {
        int n = s.length();
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)){
                map.get(c).add(i);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(c, list);
            }
        }
        int ans = 1;
        int[] dp = new int[n];
        for(int i = n - 1; i >= 0; i--){
            char c = s.charAt(i);
            int start = (c - k) < 'a' ? 'a' : c - k, end = (c + k) > 'z' ? 'z' : c + k;
            int max = 1;
            for (int j = start; j <= end; j++) {
                char mc = (char) j;
                if (map.containsKey(mc)) {
                    int index = bigger(map.get(mc), i);
                    if (index == -1){
                        continue;
                    }
                    max = Math.max(max, dp[index] + 1);
                }
            }
            dp[i] = max;
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
    private static int bigger(List<Integer> list, int goal){
        int l = 0, r = list.size() - 1;
        while (l < r){
            int m = (l + r) / 2;
            if (list.get(m) <= goal){
                l = m + 1;
            }else {
                r = m;
            }
        }
        return list.get(l) <= goal ? -1 : list.get(l);
    }
}
